package LeetCodeHot100TopInterview;

import java.util.LinkedList;
import java.util.List;
//前缀树结构
class TrieNode {
    //节点后续节点
    TrieNode[] nexts;
    //需要统计的指标
    //通过该字符个数
    int pass;
    //以该字符结尾个数
    int end;

    public TrieNode() {
        this.pass = 0;
        this.end = 0;
        //26代表这个节点后续最多有26条路，分别对应26个小写字母
        nexts = new TrieNode[26];
    }
}

class Trie{
    private TrieNode root;

    public Trie() {
        this.root = new TrieNode();
    }

    //前缀树字符搜索(word这个单词之前加入过几次) O(n)

    public int search(String word) {
        char[] chars = word.toCharArray();
        TrieNode TrieNode = this.root;
        int index = 0;
        for (int i = 0; i < chars.length; i++) {
            //确定下标
            index = chars[i] - 'a';
            if (TrieNode.nexts[index] == null) return 0;
            //TrieNode指针指到下一个节点
            TrieNode = TrieNode.nexts[index];
        }
        return TrieNode.end;
    }


    //前缀树字符插入 O(n)
    public void insert(String word) {
        char[] chars = word.toCharArray();
        TrieNode TrieNode = this.root;
        TrieNode.pass++;
        int index = 0;
        for (int i = 0; i < chars.length; i++) {
            index = chars[i] - 'a';
            if (TrieNode.nexts[index] == null) {
                TrieNode.nexts[index] = new TrieNode();
            }
            TrieNode = TrieNode.nexts[index];
            TrieNode.pass++;
        }
        TrieNode.end++;
    }


    //前缀树字符删除  O(n)
    public void delete(String word) {
        if (search(word) != 0) {
            char[] chars = word.toCharArray();
            TrieNode TrieNode = this.root;
            TrieNode.pass--;
            int index = 0;
            for (int i = 0; i < chars.length; i++) {
                index = chars[i] - 'a';
                //从树的结构看，如果最终到达的是叶子节点，置空返回即可，不懂画图
                if (--TrieNode.nexts[index].pass == 0) {
                    TrieNode.nexts[index] = null;
                    return;
                }
                TrieNode = TrieNode.nexts[index];
                //TrieNode.pass-- ;在if里已经优化了，可以省略
            }
            TrieNode.end--;
        }
    }
}

public class Q139_WordBreak{
//    输入: s = "leetcode", wordDict = ["leet", "code"]
//    输出: true
//    解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"

    //经典前缀树
    public boolean wordBreak(String s, List<String> wordDict) {
        Trie root = new Trie();
        Trie bak = null;
        //插入前缀树
        for (String s1 : wordDict) {
            bak = root;
            bak.insert(s1);
        }
//        int left = 0;
//        int right = 0;
//        while (right != s.length() + 1){
//            if (root.search(s.substring(left, right)) != 0){
//                sb.append(s.substring(left, right));
//                left = right;
//                continue;
//            }
//            right ++;
//        }
        int len = s.length();
        boolean dp[] = new boolean[len + 1];
        dp[len] = true;
        for (int i = s.length() - 1; i > -1; i--) {
            for (int j = i; j < s.length() ; j++) {
                if (root.search(s.substring(i, j + 1)) != 0 && dp[j + 1]){
                    dp[i] = true;
                }
            }
        }
        return dp[0];
    }

    public static void main(String[] args) {
        String s = "leetcode";
        List<String> wordDict = new LinkedList<>();
        wordDict.add("leet");
        wordDict.add("code");
        Q139_WordBreak fun = new Q139_WordBreak();
        System.out.println(fun.wordBreak(s, wordDict));
//        System.out.println('l' - 'a');
    }
}
